package com.algorithm.arraylist;

import java.util.*;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.function.Consumer;

/**
 * @author xiwai [hww282306@alibaba-inc.com]
 * @version 1.0
 * @date 2020/9/22 8:21 下午
 */
public class MyArrayList<E> implements List<E> {

    private Object[] elements;
    private int capacity;
    private int size;

    public MyArrayList() {
        capacity = 8;
        size = 0;
        elements = new Object[capacity];
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean contains(Object o) {
        if (o == null) {
            return false;
        }
        for (Object element : elements) {
            if (Objects.equals(element, o)) {
                return true;
            }
        }
        return false;
    }

    @Override
    public Object[] toArray() {
        Object[] array = new Object[size];
        System.arraycopy(elements, 0, array, 0, size);
        return array;
    }

    @Override
    public <T> T[] toArray(T[] a) {
        if (a.length < size) {
            throw new IllegalArgumentException("input array is too small");
        }
        System.arraycopy(elements, 0, a, 0, size);
        return a;
    }

    @Override
    public boolean add(E e) {
        if (size == capacity && !grow()) {
            // 扩容失败
            return false;
        }
        elements[size++] = e;
        return true;
    }

    @Override
    public boolean remove(Object o) {
        int index = indexOf(o);
        if (index == -1) {
            return false;
        }
        System.arraycopy(elements, index + 1, elements, index, size - index - 1);
        elements[--size] = null;
        return true;
    }

    public static void main(String[] args) {
        int[] i = {0,1,2,3,4};
        int[] b = new int[5];
        System.arraycopy(i, 1, b, 0, 3);
        System.out.println(Arrays.toString(b));
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        for (Object o : c) {
            if (!this.contains(o)) {
                return false;
            }
        }
        return true;
    }

    @Override
    public boolean addAll(Collection<? extends E> c) {
        if (capacity - size < c.size() && !grow()) {
            return false;
        }
        for (E e : c) {
            this.add(e);
        }
        return true;
    }

    @Override
    public boolean addAll(int index, Collection<? extends E> c) {
        if (capacity - index + 1 < c.size() && !grow()) {
            return false;
        }
        int i = 0;
        for (E e : c) {
            this.add(index + i++, e);
        }
        return true;
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        for (Object o : c) {
            this.remove(o);
        }
        return true;
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        // todo
        return false;
    }

    @Override
    public void clear() {
        elements = new Object[capacity];
    }

    @Override
    public E get(int index) {
        if (index >= size) {
            throw new ArrayIndexOutOfBoundsException();
        }
        return (E) elements[index];
    }

    @Override
    public E set(int index, E element) {
        if (index >= size) {
            throw new ArrayIndexOutOfBoundsException();
        }
        Object element1 = elements[index];
        elements[index] = element;
        return (E)element1;
    }

    @Override
    public void add(int index, E element) {
        throw new UnsupportedOperationException();
    }

    @Override
    public E remove(int index) {
        if (index >= size) {
            throw new ArrayIndexOutOfBoundsException();
        }
        Object element = elements[index];
        System.arraycopy(elements, index + 1, elements, index, size - index - 1);
        elements[--size] = null;
        return (E) element;
    }

    @Override
    public int indexOf(Object o) {
        for (int i = 0; i < elements.length; i++) {
            if (Objects.equals(o, elements[i])) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public int lastIndexOf(Object o) {
        for (int i = size - 1; i >= 0; i--) {
            if (Objects.equals(o, elements[i])) {
                return i;
            }
        }
        return -1;
    }

    @Override
    public ListIterator<E> listIterator() {
        // todo
        return null;
    }

    @Override
    public ListIterator<E> listIterator(int index) {
        // todo
        return null;
    }

    @Override
    public List<E> subList(int fromIndex, int toIndex) {
        // todo
        return null;
    }

    @Override
    public Iterator<E> iterator() {
        // todo
        return new Iterator<E>() {
            int index = -1;
            int next = 0;

            @Override
            public boolean hasNext() {
                return next >= 0;
            }

            @Override
            public E next() {
                return MyArrayList.this.get(index++);
            }

            @Override
            public void remove() {
                MyArrayList.this.remove(index);
                index--;
                next--;
            }

            @Override
            public void forEachRemaining(Consumer<? super E> action) {
                for (Object element : MyArrayList.this.elements) {
                    action.accept((E) element);
                }
            }
        };
    }

    private AtomicBoolean growFlag = new AtomicBoolean();

    /**
     * 表扩容
     * 扩容成原来的两倍 或者  Integer.MAX_VALUE
     * 同时允许一个扩容操作 如果正在执行扩容操作 则返回false
     * 如果无法扩容 则抛出数组已满异常
     * @return
     */
    private boolean grow() {
        if (!growFlag.compareAndSet(false, true)) {
            // 正在扩容
            return false;
        }
        if (capacity == Integer.MAX_VALUE) {
            throw new NegativeArraySizeException("list is full");
        }
        int threshold = Integer.MAX_VALUE >> 1;
        int newCapacity;
        if (capacity < threshold) {
            newCapacity = capacity << 1;
        } else {
            newCapacity = Integer.MAX_VALUE;
        }
        Object[] newElements = new Object[newCapacity];
        System.arraycopy(elements, 0, newElements, 0, size);
        capacity = newCapacity;
        elements = newElements;
        // 扩容结束 释放锁标记
        growFlag.set(false);
        return true;
    }
}
